#include <iostream>
#include <sstream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#include <random>
#include <getopt.h>
#include <sys/stat.h>
#include "config-fnt.h"
#include "graph.priv.h"
#include "stream.h"
#include "public/utils.h"

/* Options */
static const char* opts=":o:hv";
static const struct option opts_long[]=
{
	{"output", 1, nullptr, 'o'},
	{"help", 0, nullptr, 'h'},
	{"version", 0, nullptr, 'v'},
	{nullptr, 0, nullptr, 0}
};

/* Print version information and exit */
void version(const char* name) {
	std::cout<<name<<" (" PACKAGE_NAME_LONG ") " PACKAGE_VERSION "\n";
	std::cout<<"Copyright (C) 2015-2016 " PACKAGE_ORG "\n";
	std::cout<<"License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>\n\n";
	std::cout<<"Written by: " PACKAGE_AUTHORS "\n";
	exit(0);
}
// //
/* Print usage information and exit */
void usage(const char* name, int ecode) {
	if(ecode) {
		std::cerr<<"Try '"<<name<<" --help' for more information.\n";
		exit(ecode);
	}
	std::cout<<"Usage: "<<name<<" [OPTION]... [FNT_FILE]...\n";
	std::cout<<
		"Join FNT files.\n\n"
		"Options:\n"
		"  -o, --output=FILE [OPTIONAL] Save joined files to FILE. By default,\n"
		"                       save to standard output.\n\n"
		"  -h, --help        [OPTIONAL] Print this help, and do nothing else.\n"
		"  -v, --version     [OPTIONAL] Print version information and exit.\n\n"
		"Report bugs to <" PACKAGE_BUGREPORT ">\n"
		PACKAGE_NAME_LONG " home page: <" PACKAGE_URL ">\n";
	exit(ecode);
}

Graph load_graph(const char* filename, std::vector<std::string>& header) {
	Graph gr=GraphPriv::alloc();
	try {
		InputStream fs;
		if(!fs.open(filename))
			throwError("Failed to open file.");
		fs.precision(13);
		fs.setf(std::ios::scientific);

		std::string line;
		std::getline(fs, line);
		if(!fs)
			throwError("Failed to read magic header");
		bool gzipped=false;
		if(line==FNTZ_MAGIC) {
			gzipped=true;
		} else if(line!=FNT_MAGIC) {
			throwError("Wrong magic: ", line);
		}
		header.push_back(line);

		std::getline(fs, line);
		if(!fs)
			throwError("Failed to read URL line");
		while(line!="BEGIN_TRACING_DATA") {
			header.push_back(line);
			std::getline(fs, line);
			if(!fs)
				throwError("Failed to read line");
		}

		if(gzipped) {
			if(!fs.pushGzip())
				throwError("Failed to start decompressing");
		}
		auto gp=GraphPriv::get(gr);
		gp->load(fs);
		if(gzipped) {
			if(!fs.pop())
				throwError("Failed to finish decompressing");
		}
		if(!fs.close())
			throwError("Failed to close file.");

		gp->updateModel();
	} catch(const std::exception& e) {
		printMessage(e.what());
		GraphPriv::free(gr);
	}
	return gr;
}
bool save_graph(Graph gr, OutputStream& fs, const std::vector<std::string>& header) {
	bool ret=true;
	try {
		fs.precision(13);
		fs.setf(std::ios::scientific);

		bool gzipped=false;
		if(header[0]==FNTZ_MAGIC)
			gzipped=true;

		const std::vector<std::string> stringsToSkip{
			"core.current.",
			"core.target."
		};
		for(auto& l: header) {
			bool skip=false;
			for(auto& s: stringsToSkip) {
				if(l.compare(0, s.length(), s)==0) {
					skip=true;
					break;
				}
			}
			if(skip)
				continue;
			fs<<l<<'\n';
			if(!fs)
				throwError("Failed to write line");
		}

		fs<<"BEGIN_TRACING_DATA"<<'\n';
		if(!fs)
			throwError("Failed to write data start mark");

		if(gzipped) {
			if(!fs.pushGzip())
				throwError("Failed to start compressing");
		}
		GraphPriv::get(gr)->save(fs);
		if(gzipped) {
			if(!fs.pop())
				throwError("Failed to finish compressing");
		}
		if(!fs.close())
			throwError("Failed to close file");
	} catch(const std::exception& e) {
		ret=false;
	}
	return ret;
}

static int cmp_point(const Point& a, const Point& b) {
	if(a._x<b._x)
		return -1;
	if(a._x>b._x)
		return 1;
	if(a._y<b._y)
		return -1;
	if(a._y>b._y)
		return 1;
	if(a._z<b._z)
		return -1;
	if(a._z>b._z)
		return 1;
	if(a._r<b._r)
		return -1;
	if(a._r>b._r)
		return 1;
	if(a.m<b.m)
		return -1;
	if(a.m>b.m)
		return 1;
	return 0;
}

static int cmp_edge(Edge a, Edge b) {
	auto epa=EdgePriv::get(a);
	auto epb=EdgePriv::get(b);
	if(epa->type<epb->type)
		return -1;
	if(epa->type>epb->type)
		return 1;
	if(epa->points.size()<epb->points.size())
		return -1;
	if(epa->points.size()>epb->points.size())
		return 1;
	auto n=epa->points.size();
	for(size_t i=0; i<n; i++) {
		auto r=cmp_point(epa->points[i], epb->points[i]);
		if(r<0)
			return -1;
		if(r>0)
			return 1;
	}
	return 0;
}

static int cmp_edge_idx(Edge a, Edge b) {
	auto epa=EdgePriv::get(a);
	auto epb=EdgePriv::get(b);
	if(epa->index<epb->index)
		return -1;
	if(epa->index>epb->index)
		return 1;
	return 0;
}

typedef std::pair<Edge, bool> EdgeEnd;
static int cmp_edge_end(const EdgeEnd& a, const EdgeEnd& b) {
	auto r=cmp_edge_idx(a.first, b.first);
	if(r<0)
		return -1;
	if(r>0)
		return 1;
	if(!a.second && b.second)
		return -1;
	if(a.second && !b.second)
		return 1;
	return 0;
}

static int cmp_vert(Vertex a, Vertex b) {
	auto vpa=VertexPriv::get(a);
	auto vpb=VertexPriv::get(b);
	if(!vpa->finished && vpb->finished)
		return -1;
	if(vpa->finished && !vpb->finished)
		return 1;

	if(vpa->neighbors.size()<vpb->neighbors.size())
		return -1;
	if(vpa->neighbors.size()>vpb->neighbors.size())
		return 1;
	auto n=vpa->neighbors.size();
	for(size_t i=0; i<n; i++) {
		auto r=cmp_edge_end(vpa->neighbors[i], vpb->neighbors[i]);
		if(r<0)
			return -1;
		if(r>0)
			return 1;
	}
	return 0;
}

static int cmp_nrn(Tree a, Tree b) {
	auto vpa=VertexPriv::get(a.root());
	auto vpb=VertexPriv::get(b.root());
	if(vpa->index<vpb->index)
		return -1;
	if(vpa->index>vpb->index)
		return 1;
	return 0;
}

struct Component {
	std::vector<size_t> edges;
	std::vector<size_t> verts;
	std::vector<size_t> nrns;
};

void reorder_component(Component* comp, GraphPriv* grp) {
	std::sort(comp->edges.begin(), comp->edges.end(), [grp](size_t a, size_t b)->bool { return cmp_edge(grp->edges[a], grp->edges[b])<0; });
	for(size_t i=0; i<comp->edges.size(); i++) {
		auto ep=EdgePriv::get(grp->edges[comp->edges[i]]);
		ep->index=i;
	}
	for(size_t i=0; i<comp->verts.size(); i++) {
		auto vp=VertexPriv::get(grp->vertices[comp->verts[i]]);
		std::sort(vp->neighbors.begin(), vp->neighbors.end(), [](const EdgeEnd& a, const EdgeEnd& b)->bool { return cmp_edge_end(a, b)<0; });
	}
	std::sort(comp->verts.begin(), comp->verts.end(), [grp](size_t a, size_t b)->bool { return cmp_vert(grp->vertices[a], grp->vertices[b])<0; });
	for(size_t i=0; i<comp->verts.size(); i++) {
		auto ep=VertexPriv::get(grp->vertices[comp->verts[i]]);
		ep->index=i;
	}
	std::sort(comp->nrns.begin(), comp->nrns.end(), [grp](size_t a, size_t b)->bool { return cmp_nrn(grp->trees[a], grp->trees[b])<0; });
}

bool eq_component(Component* a, Component* b, GraphPriv* grp) {
	if(a->edges.size()!=b->edges.size())
		return false;
	for(size_t i=0; i<a->edges.size(); i++) {
		auto r=cmp_edge(grp->edges[a->edges[i]], grp->edges[b->edges[i]]);
		if(r!=0)
			return false;
	}
	if(a->verts.size()!=b->verts.size())
		return false;
	for(size_t i=0; i<a->verts.size(); i++) {
		auto r=cmp_vert(grp->vertices[a->verts[i]], grp->vertices[b->verts[i]]);
		if(r!=0)
			return false;
	}
	if(a->nrns.size()!=b->nrns.size())
		return false;
	for(size_t i=0; i<a->nrns.size(); i++) {
		auto r=cmp_nrn(grp->trees[a->nrns[i]], grp->trees[b->nrns[i]]);
		if(r!=0)
			return false;
	}
	return true;
}


std::vector<Component> find_components(Graph gr) {
	std::vector<Component> comps;
	auto n=gr.vertices().size();
	std::vector<bool> edg_dirty(gr.edges().size(), false);
	std::vector<bool> vert_dirty(n, false);
	std::vector<bool> nrn_dirty(gr.trees().size(), false);
	while(true) {
		size_t seed=SIZE_MAX;
		for(size_t i=0; i<n; i++) {
			if(!vert_dirty[i]) {
				seed=i;
				break;
			}
		}
		if(seed==SIZE_MAX)
			break;
		Component comp{{}, {}, {}};
		std::queue<size_t> que{};
		que.push(seed);
		while(!que.empty()) {
			auto i=que.front();
			que.pop();
			auto v=gr.vertices()[i];
			if(!vert_dirty[i]) {
				comp.verts.emplace_back(i);
				for(auto& p: v.neighbors()) {
					auto v1=p.second?p.first.leftVertex():p.first.rightVertex();
					que.push(v1.index());
				}
				auto nrn=v.tree();
				if(nrn && nrn.root()==v) {
				}
				vert_dirty[i]=true;
			}
		}
		for(auto i: comp.verts) {
			auto v=gr.vertices()[i];
			for(auto& p: v.neighbors()) {
				auto j=p.first.index();
				if(!edg_dirty[j]) {
					comp.edges.push_back(j);
					edg_dirty[j]=true;
				}
			}
		}
		for(auto i: comp.verts) {
			auto nrn=gr.vertices()[i].tree();
			if(nrn) {
				auto j=nrn.index();
				if(!nrn_dirty[j]) {
					comp.nrns.push_back(j);
					nrn_dirty[j]=true;
				}
			}
		}
		comps.push_back(std::move(comp));
	}
	for(auto v: edg_dirty) {
		if(!v)
			throwError("Untouched edge");
	}
	for(auto v: vert_dirty) {
		if(!v)
			throwError("Untouched vertex");
	}
	for(auto v: nrn_dirty) {
		if(!v)
			throwError("Untouched neuron");
	}
	return comps;
}

int main(int argc, char* argv[]) {
	const char* output=nullptr;

	// Parse options
	int opt;
	int prev_optind=optind;
	while((opt=getopt_long(argc, argv, opts, opts_long, nullptr))!=-1) {
		switch(opt) {
			case '?':
				std::cerr<<argv[0]<<": unrecognized option '";
				std::cerr<<argv[prev_optind]<<"'\n";
				usage(argv[0], -1);
			case ':':
				std::cerr<<argv[0]<<": option '"<<argv[prev_optind];
				std::cerr<<"' requires an argument\n";
				usage(argv[0], -1);
			case 'h':
				usage(argv[0], 0);
			case 'v':
				version(argv[0]);
			case 'o':
				output=optarg;
				break;
			default:
				std::cerr<<"Unexpected error.\n";
				usage(argv[0], -1);
		}
		prev_optind=optind;
	}

	if(optind>=argc) {
		std::cerr<<"No input FNT files specified.\n";
		usage(argv[0], -1);
	}

	std::vector<std::string> header;
	auto gr=GraphPriv::alloc();
	auto gp=GraphPriv::get(gr);
	for(auto i=optind; i<argc; i++) {
		std::vector<std::string> header_discard;
		auto graph=load_graph(argv[i], i==optind?header:header_discard);
		if(!graph) {
			std::cerr<<"Failed to load FNT file.\n";
			return -1;
		}
		for(auto v: graph.vertices()) {
			gp->vertices.push_back(v);
		}
		for(auto v: graph.edges()) {
			gp->edges.push_back(v);
		}
		for(auto v: graph.trees()) {
			gp->trees.push_back(v);
		}
		GraphPriv::free(graph);
	}

	{
#if 0
		std::default_random_engine rng{};
		std::shuffle(gp->edges.begin(), gp->edges.end(), rng);
		std::shuffle(gp->vertices.begin(), gp->vertices.end(), rng);
		std::shuffle(gp->trees.begin(), gp->trees.end(), rng);
#endif

		gp->updateModel();
		auto comps=find_components(gr);
		for(size_t k=0; k<comps.size(); k++) {
			reorder_component(&comps[k], gp);
		}
		for(size_t k=0; k<comps.size(); k++) {
			for(size_t i=0; i<comps[k].edges.size(); i++) {
				printMessage(k, ": ", comps[k].edges[i]);
			}
		}
		for(size_t k=1; k<comps.size(); k++) {
			size_t dup=SIZE_MAX;
			for(size_t prev=0; prev<k; prev++) {
				if(eq_component(&comps[prev], &comps[k], gp)) {
					dup=prev;
					break;
				}
			}
			if(dup!=SIZE_MAX) {
				printMessage("DUP: ", dup, ", ", k);
				for(size_t i=0; i<comps[k].nrns.size(); i++) {
					auto na=TreePriv::get(gp->trees[comps[dup].nrns[i]]);
					auto nb=TreePriv::get(gp->trees[comps[k].nrns[i]]);
					if(na->name!=nb->name) {
						if(na->name.find(nb->name)!=std::string::npos) {
						} else if(nb->name.find(na->name)!=std::string::npos) {
							na->name=nb->name;
						} else {
							na->name+=", ";
							na->name+=nb->name;
						}
					}
				}

				for(auto i: comps[k].edges) {
					auto e=gp->edges[i];
					gp->edges[i]=Edge{};
					EdgePriv::free(e);
				}
				for(auto i: comps[k].verts) {
					auto e=gp->vertices[i];
					gp->vertices[i]=Vertex{};
					VertexPriv::free(e);
				}
				for(auto i: comps[k].nrns) {
					auto e=gp->trees[i];
					gp->trees[i]=Tree{};
					TreePriv::free(e);
				}
				comps[k].edges.clear();
				comps[k].verts.clear();
				comps[k].nrns.clear();
			}
		}
		auto ee=std::remove(gp->edges.begin(), gp->edges.end(), Edge{});
		gp->edges.resize(ee-gp->edges.begin());
		auto ve=std::remove(gp->vertices.begin(), gp->vertices.end(), Vertex{});
		gp->vertices.resize(ve-gp->vertices.begin());
		auto te=std::remove(gp->trees.begin(), gp->trees.end(), Tree{});
		gp->trees.resize(te-gp->trees.begin());

		for(auto e: gp->edges) {
			auto ep=EdgePriv::get(e);
			ep->type=0;
		}
		gp->updateModel();
	}


	OutputStream gzw;
	if(output) {
		if(!gzw.open(output))
			throwError("Failed to open file");
	} else {
		if(!gzw.open(stdout))
			throwError("Failed to open file");
	}

	bool ret=save_graph(gr, gzw, header);
	if(!ret) {
		if(output) {
			std::cerr<<"Failed to save: "<<output<<"\n";
		} else {
			std::cerr<<"Failed to save to stdout\n";
		}
	}

	GraphPriv::free(gr);

	return 0;
}

